package org.laizili.solution.leetcode;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/find-and-replace-pattern/">890. 查找和替换模式</a>
 */
public class Problem890 {
    private static class Solution {
        public List<String> findAndReplacePattern(String[] words, String pattern) {
            int len = pattern.length();
            /*
              小写字母表可以用数组优化
              table = int[26];
              vis = int[26]
            */
            Set<Character> seenCharset = new HashSet<>(len);
            HashMap<Character, Character> transform = new HashMap<>(len);
            List<String> res = new ArrayList<>();
            for (String word : words) {
                seenCharset.clear();
                transform.clear();
                boolean valid = true;
                for (int i = 0; i < len; i++) {
                    // t(p_i) = w_i <=> t'(w_i) = p_i
                    char wi = word.charAt(i);
                    char pi = pattern.charAt(i);
                    if (!transform.containsKey(wi)) {
                        if (!seenCharset.contains(pi)) {
                            //不存在该映射
                            transform.put(word.charAt(i), pattern.charAt(i));
                            seenCharset.add(pi);
                        } else {
                            valid = false;
                            break;
                        }
                    } else if (transform.get(wi) != pi) {
                        valid = false;
                        break;
                    }
                }
                if (valid)
                    res.add(word);
            }
            return res;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().findAndReplacePattern(new String[]{"aa", "bb", "ab", "cd"}, "aa"));
    }
}
